1. Field of the Invention
This invention is related to the field of deadlock prevention in communications between coherent agents in a distributed coherent system.
2. Description of the Related Art
In various systems in which multiple agents may initiate operations, system deadlock is a possibility. Particularly, operations may be part of a complex set of operations required to complete a communication between agents in the system. In such cases, the operations may have various dependencies on one another, requiring operations to be able to bypass one another at the communication medium to complete the overall communication. If the bypassing is not possible, deadlock may occur. Thus, mechanisms to prevent deadlock are needed.
One mechanism used to prevent deadlock is virtual channels. A virtual channel may be though of as an abstract connection over a communication medium. Each virtual channel used on the communication medium is defined to flow over the communication medium logically independent of the other virtual channels on that communication medium. For example, buffers on each side of the communication medium may be defined for the virtual channels, and separate (independent) flow controls may be used for each virtual channel. Thus, if one virtual channel is blocked (e.g. due to a lack of receiving buffers on the other end of the communication medium, or for some logical reason such as a protocol requirement or dependency), other virtual channels may still communicate over the communication medium. In some cases, a given virtual channel may be implemented as a separate physical communication medium. In other cases, however, virtual channels may share at least a portion of a communication medium between a source and a destination.
By assigning operations that may have dependencies on each other to separate virtual channels, the operations may be permitted to occur in the correct order since the virtual channels may not block each other due to physical or resource constraints. That is, if a first operation is stalled due to a dependency on a second operation, the fact that the second operation is in a different virtual channel than the first operation ensures that the second operation will not be blocked from transmission by the first operation.
In some cases, false dependencies between operations may occur. For example, such false dependencies may occur if there is ambiguity as to the dependency (or lack thereof). If ambiguity may not be resolved at the time an operation is to be placed in a virtual channel, then a false dependency may be created to ensure that the coherency mechanism works correctly for either resolution of the ambiguity. The dependency is false if the dependency is created (to resolve the ambiguity) but in reality the dependency does not exist. False dependencies may lead to deadlock in the system even with the use of virtual channels.